\documentclass[a4paper]{article}
\usepackage{etex}
\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{url}
\usepackage{subfig}
\usepackage{clrscode}
\usepackage[table]{xcolor}
\usepackage{color}
\usepackage{listings}
\usepackage{courier}
\usepackage{float}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{pgfplotstable}
%\usepackage{natbib}


\title{Advanced Algorithms \\ Project 2}
\author{David Falk, Klaus Nicosia, Marcus Öberg\\
dfa@kth.se, nicosia@kth.se, marcusob@kth.se}

%\pgfplotstableset{fixed zerofill,precision=3}
\pgfplotsset{width=12cm, height=7.5cm}
%\setcitestyle{square,numbers}
\begin{document}
\maketitle
\thispagestyle{empty}
\newpage



% Abstract.
\begin{abstract}
Several heuristics and algorithms can be used to find a tour that is a good solution to the Traveling Salesman Problem (TSP). A good solution is a tour that is close to the optimal (shortest) tour.

This project concerns an exercise that consisted of solving the Euclidean TSP in two dimensions for 50 instances. These instances have a maximum of 1000 cities and must be solved in under 2 seconds each.

Theory behind these and other heuristics and algorithms is presented to give a good picture of the exercise in question and to some extent the TSP itself. Data structures useful for TSP, construction heuristics, local optimization algorithms and the effective implementation of these are discussed. The results are presented together with conclusions and comments on how further improvements could be made.

We show the expected fact that the local optimization algorithm 3-Opt outperforms 2-Opt and that it yields a reasonably good solution. We also show that the nearest neighbor construction heuristic provides a seemingly good initial tour for the use in 3-Opt.
\end{abstract}



\thispagestyle{empty}
\newpage
\tableofcontents
\thispagestyle{empty}
\newpage
\setcounter{page}{4}


% Introduction.
\section{Introduction}
In the \emph{Traveling Salesman Problem (TSP)} we are given a set $\left\{c_0, c_1, ..., c_{N - 1} \right\}$ of $N$ \emph{cities} $c_i$, $0 \leq i < N$ and a \emph{distance} $d(c_i, c_j)$ between every pair of distinct cities $c_i$ and $c_j$ ($i \neq j$) \cite{tsp}. The task is to find the shortest \emph{tour} that starts and ends in the same city and visits every city exactly once. Thus we want to find the permutation $\pi$ of the cities that minimize the \emph{tour length} (total traveling distance):

\begin{displaymath}
\sum_{i=0}^{N - 2}
d \left(c_{\pi(i)}, c_{\pi(i + 1)} \right)
+ d \left(c_{\pi(N - 1)}, c_{\pi(0)} \right).
\end{displaymath}

The important special case of TSP that concerns this project is the \emph{Euclidean TSP} where the cities are points in \emph{Euclidean space}. More specifically, this concerns the two dimensional version in which the points $c_i = (x_i, y_i)$ lie in the plane and the distances are the \emph{Euclidean distances}:

\begin{displaymath}
d(c_i, c_j) = \sqrt{\left(x_i - x_j \right)^2 + \left(y_i - y_j \right)^2}.
\end{displaymath}
Note that this version is also a \emph{symmetric TSP} in the sense that the distances satisfies $d(c_i, c_j) = d(c_j, c_i)$ for $0 \leq i, j < N$. Further more, the important \emph{triangle inequality} $d(c_i, c_j) \leq d(c_i, c_k) + d(c_k, c_j)$ holds for $0 \leq i, j, k < N$. 


An \emph{instance} of the problem can be represented as a \emph{complete undirected graph} where the cities are represented by the \emph{vertices} (\emph{nodes}) and the distances as \emph{weights} on the \emph{edges}. The tour can be represented as a \emph{directed subgraph} of the problem graph.

TSP is one of the most studied NP-hard problems and have a wide range of useful applications.



% Problem.
\section{Problem}
The goal for this project was to create a program that finds solutions (tours) for two dimensional Euclidean TSP. These tours should be as close as possible to the optimal tour.

There are 50 instances, with a maximum of 1000 cities, to solve that are provided by the grading and evaluation system \emph{Kattis}. Kattis have some restrictions on the execution of the program, namely a \emph{time limit} of 2 seconds per instance and a \emph{memory limit} of 32 MB.

This problem was solved by using the programming language Java, which is one of the languages supported by Kattis.

Kattis calculates a \emph{score}, which is a number between 0 and 50 (\emph{points}, p) for the tour generated by our program. Each instance is rewarded by a score between 0 and 1, where a higher score is better. 50 points would mean that all solutions are optimal.


\pagebreak
% General Theory.
\section{General Theory}


\subsection{The 2-change Operation}
\label{2-change}
The manipulation move for 2-Opt described below are based on the \emph{2-change} operation. A 2-change operation manipulates the current tour by replacing the directed edges $(a, b)$ and $(d, c)$ with the directed edges $(b, c)$ and $(a, d)$. Note that the direction of the tour between city $b$ and $d$ has to be reversed for the resulting tour to be valid. Figure \ref{fig:2-change_original} shows the original tour and figure \ref{fig:2-change_result} shows the resulting tour. Note that the figures are schematic such that the distances are not represented geometrically.

\begin{figure}[H]
  \centering
  \subfloat[]{
    \label{fig:2-change_original}
    \includegraphics[width=0.45\textwidth]{Pics/2-change_orig.png}}
  \hspace{10pt}
  \subfloat[]{
    \label{fig:2-change_result}
    \includegraphics[width=0.45\textwidth]{Pics/2-change_result.png}}                
  \caption{\textbf{(a)} The original tour. The edges to be replaced are dotted. \textbf{(b)} The resulting tour. The new edges are dotted.}
  \label{fig:2-change}
\end{figure}


\subsection{The 3-change Operation}
\label{3-change}
The manipulation move for 3-Opt described below are based on the \emph{3-change} operation. A \emph{3-change} operation manipulates the current tour by replacing the directed edges $(a, b)$, $(d, c)$ and $(f, e)$. There are four different ways that these edges can be replaced. These are:
\begin{enumerate}
\item $(a, c)$, $(f, b)$ and $(d, e)$ (see figure \ref{fig:3-change_result1})
\item $(a, f)$, $(c, b)$ and $(d, e)$ (see figure \ref{fig:3-change_result2})
\item $(a, d)$, $(c, e)$ and $(b, f)$ (see figure \ref{fig:3-change_result3})
\item $(a, c)$, $(b, e)$ and $(f, d)$ (see figure \ref{fig:3-change_result4})
\end{enumerate}
As in 2-change (\ref{2-change}) the direction of the tour between some cities have to be reversed for the resulting tour to be valid. Figure \ref{fig:3-change_original} shows the original tour and figure \ref{fig:3-change_result} shows the four resulting tours. Note that the figures are schematic such that the distances are not represented geometrically.

\begin{figure}[H]
  \centering  
  \includegraphics[width=0.45\textwidth]{Pics/3-change_orig.png}
  \caption{The original tour. The edges to be replaced are dotted.}
  \label{fig:3-change_original}
\end{figure}

\begin{figure}[H]
  \centering
  \subfloat[]{
    \label{fig:3-change_result1}
    \includegraphics[width=0.45\textwidth]{Pics/3-change_result1.png}}
  \hspace{10pt}
  \subfloat[]{
    \label{fig:3-change_result2}
    \includegraphics[width=0.45\textwidth]{Pics/3-change_result2.png}}
    \vspace{20pt}
    \subfloat[]{
    \label{fig:3-change_result3}
    \includegraphics[width=0.45\textwidth]{Pics/3-change_result3.png}}
    \hspace{10pt} 
    \subfloat[]{
    \label{fig:3-change_result4}
    \includegraphics[width=0.45\textwidth]{Pics/3-change_result4.png}}
  \caption{The four resulting tours. The new edges are dotted.}
  \label{fig:3-change_result}
\end{figure}

\pagebreak
\subsection{The Tour Data Structure}
\label{TDS}
2-Opt and 3-Opt requires that the following functions can be done on the data structure that represents the tour \cite{dtsp}:
\begin{itemize}
\item \proc{Next}$(a)$ returns the city that follows $a$ in the current tour.
\item \proc{Prev}$(a)$ returns the city that precedes $a$ in the current tour.
\item \proc{Between}$(a, b , c)$ returns \const{true} if $b$ is reached before $c$, when starting in city $a$ and traversing the tour, otherwise returns \const{false}. In other words $b$ is \emph{between} $a$ and $c$ in the current tour.
\item \proc{Flip}$(a, b, c, d)$ manipulates the current tour by replacing the directed edges $(a, b)$ and $(d, c)$ with the directed edges $(b, c)$ and $(a, d)$. Thus, \proc{Flip} implements the 2-change move described in \ref{2-change} above. Note that the direction of the tour between city $b$ and $d$ has to be reversed for the resulting tour to be valid. It is assumed that $b = $ \proc{Next}$(a)$ and $c = $ \proc{Next}$(d)$.
\end{itemize}
Note that \proc{Between} is only needed for 3-Opt. Further note that it must hold that \proc{Next}(\proc{Prev}$(a))$ = \proc{Prev}(\proc{Next}$(a) ) = a$.



% Tour Construction Heuristics.
\section{Tour Construction Heuristics}
\label{tourconst}
To find a solution to the TSP one can use a \emph{successive augmentation} heuristic \cite{tsp}. The heuristic builds a solution by using a process that grows the tour from scratch and terminates when a legitimate tour is found. Such a heuristic is in the case of TSP called a \emph{tour construction} heuristic.

A few construction heuristics are presented in this chapter.


\subsection{Nearest Neighbor}
One method to construct a tour is to use the nearest neighbor method. This method is naive in the sense that it picks a starting vertex and then chooses the next vertex as the closest unused neighboring vertex. This is repeated until every vertex is in the tour. The \proc{Nearest-Neighbor} algorithm takes $O(N^2)$ time.
\begin{codebox}
\label{alg:nn}
\Procname{$\proc{Nearest-Neighbour}(G)$}
\li $\id{tour}[0] \gets$ Index from a vertex in G
\li $\id{used}[0] \gets \const{true}$
\li \For $i \gets 1$ \To $N-1$
\li \Do
    $\id{best} \gets -1$
\li \For $j \gets 0$ \To $N-1$
\li \Do
    \If $\id{used}[j] \not = \const{true} \mbox{ \textbf{and} } (best = -1$
\zi $ \mbox{ \textbf{or} } d(\id{tour}[i-1],\id{tour}[j]) < d(\id{tour}[i-1],\id{best}))$
\li \Then
\li $\id{best} \gets j$
\End
\End
\li $\id{tour}[i] \gets best$
\li $\id{used}[\id{best}] \gets \const{true}$
\End
\li \Return \id{tour}
\end{codebox}


\subsection{Greedy}
\label{greedy}
The greedy algorithm is similar to nearest neighbor. In contrast to nearest neighbor, greedy does not start at a vertex and iteratively add the closes neighbor, instead it adds the globally shortest edge to the tour with the condition that no vertex can have a degree greater then two \cite{tsp}. The algorithm ends when all vertices are of degree two and subsequently a tour have been found. The greedy algorithm has complexity $O(N^2$ log $N)$.

\subsection{Christofides}
\label{christo}
The Christofides algorithm solves TSP by creating a \emph{minimum spanning tree} from the problem graph \cite{tsp}. A minimum length matching is calculated from this minimum spanning tree and is used to create a tour. Christofides is in sense the best tour construction algorithm and has complexity $O(N^3)$.


% Local Optimization Algorithms.
\section{Local Optimization Algorithms}
Once an \emph{initial tour} exists, given or created with a construction heuristic, it can be improved upon by a \emph{local optimization algorithm} \cite{tsp}. A local optimization algorithm tries to improve the current solution by performing an \emph{exchange operation} such as a 2-change (see \ref{2-change}) or 3-change (see \ref{3-change}). If an exchange operation only is done when it improves the solution (reduces the tour length), then these \emph{adjacent} solutions will converge towards a \emph{local optimum}. This is also known as doing a \emph{local search} among the adjacent solutions.

A few local search algorithms are presented in this chapter.


\subsection{2-Optimal}
\label{2-optimal}
2-Optimal (2-Opt) is a local optimization method that is used to improve an already existing tour. This method uses the fact that in some cases you get a shorter tour with a 2-change operation (\ref{2-change}). So first pick two edges, then check if the tour gets shorter with a 2-change operation. In that case do the 2-change operation. Since the data structure implements the 2-change operation it is possible to use the \proc{Flip} manipulation. To not be forced to check the total tour length in every step it is important to do the operation in such a fashion that the rest of the tour is not affected. The \proc{Two-Optimal} algorithm described below takes $O(N)$ time given that \proc{Prev} and \proc{Next} are constant.
In general the algorithm works like this:
\begin{enumerate}
\item Take a tour  $T$ that spans every vertex in the graph.
\item Find an edge with start vertex $t_1$ and end vertex $t_2$.
\item Find an unused edge $(t_4, t_3)$ that is disjoint from $(t_1, t_2)$ ($t_3 \neq t_1 $ and $t_4 \neq t_2$ ).
\item If $d(t_1,t_3) + d(t_2,t_4) < d(t_1,t_2) + d(t_3,t_4)$ do $\proc{Flip}(t_1,t_2,t_3,t_4)$.
\end{enumerate}

\begin{figure}[H]
  \centering
  \subfloat[Before]{\label{fig:2opta}\includegraphics[width=0.45\textwidth]{Pics/2-opt_before.png}}
  \hspace{10pt}                
  \subfloat[After]{\label{fig:2optb}\includegraphics[width=0.45\textwidth]{Pics/2-opt_after.png}}
  \caption{a 2-Opt operation}
  \label{fig:2opt}
\end{figure}

\begin{codebox}
\Procname{$\proc{Two-Optimal}(T)$}
\li $\id{t_1} \gets$ A vertex from the tour $T$
\li $\id{t_2} \gets \proc{Next}(\id{t_1})$
\li \For All neighbours $v$ of $t_1$
\li \Do
$\id{t_3} \gets v$
\li $\id{t_4} \gets \proc{Prev}(\id{t_3})$
\li \If $d(t_1,t_3) + d(t_2,t_4) < d(t_1,t_2) + d(t_3,t_4)$
\li \Then Break for loop
\End
\End
\li \If $d(t_1,t_3) + d(t_2,t_4) < d(t_1,t_2) + d(t_3,t_4)$
\li \Then $\proc{Flip}(t_1,t_2,t_3,t_4)$
\End
\end{codebox}


\subsection{3-Optimal}
\label{3-optimal}
3-Optimal (3-Opt) is similar to 2-Opt but instead of replacing two edges, three edges are replaced. This becomes a little more complex because, as described in section \ref{3-change}, there are four possible ways to replace the edges in such a way so that the tour is still a valid tour. However, since we have an Euclidean graph\footnote{The graph in Euclidean TSP is complete therefore every permutation will be reached.}, three of the possibilities are equivalent (see figure \ref{fig:3opt}). It is possible to do a 3-change operation with two or three \proc{Flip} moves \cite{k_opt}. There are however four different \proc{Flip} combinations that represent the different 3-change operations in \ref{3-change}. The \proc{Flip} combination to use is determined by comparing the lengths of the resulting tours. The \proc{Three-Optimal} algorithm described below takes takes $O(N^2)$ time given that \proc{Prev} and \proc{Next} are constant.

\begin{enumerate}
\item Take a tour $T$ that spans every vertex in the graph.
\item Find an edge $(t_1,t_2)$.
\item Find an unused edge $(t_4, t_3)$ where $t_3 \neq t_2$ and $t_4 \neq t_1$.
\item Find an unused edge $(t_6, t_5)$ where $t_5 \neq [t_1, t_2, t_3]$ and $t_6 \neq [t_1, t_2,t_4]$.
\item Evaluate if any possible permutation of the edges (see figure \ref{fig:3-change_result}) improves the tour. If it does improve the tour then do the corresponding \proc{Flip} combination.
\end{enumerate}


\begin{figure}[H]
  \centering
  \subfloat[Before]{\label{fig:3opta}\includegraphics[width=0.3\textwidth]{Pics/3-opt_base.png}}
  \hspace{10pt}                
  \subfloat[Permutation 1]{\label{fig:3optb}\includegraphics[width=0.3\textwidth]{Pics/3-opt_0.png}}
  \hspace{10pt}           
  \subfloat[Permutation 2]{\label{fig:3optc}\includegraphics[width=0.3\textwidth]{Pics/3-opt_1.png}}
  \hspace{10pt}         
  \caption{The two different possible permutations of $T$ in 3-Opt.}
  \label{fig:3opt}
\end{figure}

The function \proc{Improving-Move} checks if one of the four tour representations described in section \ref{3-change} are shorter than the previous tour. \proc{3-change} does the 3-change operation (\ref{3-change}) that yields the shortest tour.

\begin{codebox}
\Procname{$\proc{Three-Optimal}(T)$}
\li $\id{t_1} \gets$ A vertex from the tour T
\li $\id{t_2} \gets \proc{Next}(\id{t_1})$
\li \For All neighbours $v_1$ of $t_1$
\li \Do
$\id{t_3} \gets v_1$
\li $\id{t_4} \gets \proc{Prev}(\id{t_3})$
\li \For All neighbours $v_2$ of $t_4$
\li \Do
$\id{t_5} \gets v_2$
\li $\id{t_6} \gets \proc{Prev}(\id{t_5})$
\li \If $\proc{Improving-Move}(t_1,t_2,t_3,t_4,t_5,t_6)$
\li \Then Break for loop
\End
\End
\li Break for loop
\End
\li \If $\proc{Improving-Move}(t_1,t_2,t_3,t_4,t_5,t_6)$
\li \Then $\proc{3-change}(t_1,t_2,t_3,t_4,t_5,t_6)$
\End
\end{codebox}


\subsection{$k$-Optimal}
$k$-Optimal ($k$-Opt) uses the same basic idea as 2-Opt and 3-Opt. Instead of evaluating two or three edges, $k$ edges are evaluated, where $k$ is a positive integer. This operation can be executed with $k$ or less 2-change operations \cite{k_opt}. $k$-Opt operations with $k$ bigger than 3 does not usually yield a significantly better result and since it requires more operations it is not as efficient \cite{tsp}. For these reasons $k$-Opt is not usually not chosen as a primary optimization algorithm.


\subsection{Lin-Kernighan}
\label{lk}
Lin and Kernighan devised an algorithm 1973 that has proved to be very efficient in both running time and tour quality \cite{tsp}. It makes use of tabu lists to keep track of edges that are not available for evaluation, and employs the $k$-Opt algorithm. 


The tabu lists in the Lin-Kernighan (LK) algorithm keeps track of the edges that have been removed and the edges that have been added\footnote{Some implementations only use one of these lists.} \cite{LKHReport}. It does not allow adding a removed edge or removing an added edge. The algorithm first evaluates two edges as 2-Opt. If this won't improve the tour it continues by choosing another edge and tries 3-Opt. The algorithm continues with $k$-Opt for increasing $k$ values until no new edge can be found.


The main difference from the basic $k$-Opt operation is that instead of comparing tour path the LK algorithm compares a hamiltionian path between the start and end vertices (for example $t_1$ and $t_5$ in 3-Opt). This implies that not all chosen moves improves the total tour. The algorithm does this to avoid getting stuck in an local optimum. When no further move is possible in the new tour $T'$, due to no improvement in the hamiltonian path, and the shortest tour found, $T$, is shorter than $T'$. Then the algorithm backtracks to $T$ and evaluates other moves. $T$ is restricted to instances where only two edges have been evaluated.

According to Johnson et al. the Lin-Kernighan gave significant performance increases on all test cases while still keeping running time acceptable \cite{tsp}.



% Implementation.
\section{Implementing 2-Opt and 3-Opt Efficiently}


\subsection{Calculating Distances}
\label{precalc}
We have chosen to calculate all the distances in the beginning of the program. Since we will need all distances in the nearest neighbor algorithm and also some distances later in 2-Opt and 3-Opt this means we do not have to calculate the same distance more then once. We store all the distances in a matrix and can access these with the vertices original input index. Since the matrix will be symmetric only the upper triangle is calculated and is then mirrored to the lower triangle. The calculation of these distances has time complexity $O(N^2)$, where $N$ is the number of vertices.


\subsection{Neighbor Lists}
\label{neighbor_lists}
It is unreasonable for large $N$ values to consider all possible choices of edges in 2-Opt and 3-Opt \cite{algnotes}. Because of this and the time limit enforced by Kattis we have chosen to only consider some of the adjacent solutions in our local optimization algorithm. For a certain vertex $v$ we only consider the edges for which the other endpoint is one of the $k$ nearest neighbors of $v$, where $k$ is a fixed positive integer. The creation of the neighbor lists have a time complexity $O(kN)$, where $N$ is the number of vertices. It is possible that the local optimum found is a longer tour than a complete search would yield. This is usually not an issue in practice for typical $k$ values, such as $10 \leq k \leq 30$ \cite{tsp}.

\subsection{The Tour Data Structure}
\label{ds_theory}
Performing the tour manipulation moves can account for a considerable amount of the running time \cite{tsp}. Because of this it might be useful to improve the data structure that represents the tour.

M. L. Fredman et al. present several tour data structures \cite{dtsp}. These are: The \emph{Array} representation, \emph{Two-Level Trees}, \emph{Splay Trees} and \emph{Segment Trees}. Two-Level Trees, Splay Trees and Segment Trees are advanced data structures that are useful when the number of cities $N > 1000$. Arrays are the structure of choice for instances with $N < 1000$. The data presented by M. L. Fredman et al. for $N = 1000$ however indicates that Two-Level Trees might be slightly better. The data concerns Lin-Kernighan for which the difference should be more noticeable than for 3-Opt. We are not completely sure how the data structure would affect 2-Opt.



% Implementation.
\section{Implementation}


\subsection{General Implementation Details}

\subsubsection*{The Array Representation}
\label{array}
Due to the fact that our final implementation uses 3-Opt (as opposed to Lin-Kernighan, see \ref{ds_theory} above) and the added complexity of implementing Two-Level Trees we choose to implement the Tour Data Structure as Arrays.

The Array representation for the tour is simple. The tour is represented by the array $A$ which lists the cities in tour order; $A[i]$ is the city to be visited as number $i$ in the tour, with $A[i + 1] = $ \proc{Next}$(i)$ for $0 \leq i < N - 1$ and $A[0] = $ \proc{Next}$(A[N-1])$. To effectively implement the operations another array $B$ is created and maintained. $B$ is the inverse of $A$, that is: $A[B[i]] = B[A[i]] = c_i$, where $c_i$ is the city $i$ and $0 \leq i < N$. $B[i]$ is at what point in the tour city $i$ is visited.

The \proc{Next} and \proc{Prev} operations are straightforward and have time complexity $O(1)$. The \proc{Between} and \proc{Flip} operations require some thinking to implement. \proc{Between} also takes constant time. \proc{Flip} takes time proportional to the number of cities in the segment of the tour that needs to be reversed (see \ref{2-change} above), which in worst case is $\Theta(N)$.


\subsubsection*{Vertex Object}
The neighbor lists (as described in \ref{neighbor_lists} above) are stored in a Vertex object as unsorted arrays. We also store the initial index of each vertex as an integer in this object so that we can easily obtain the distances from the distance matrix (described in \ref{precalc} above).


\subsubsection*{Tour Visualization}
During testing the tours were visualized by creating a Java class that the tour was sent to as an argument. This visualization made it easier to find problems and provided a simple way of testing if we fixed these problems.


\subsection{Nearest Neighbor Implementation}
Our implementation of nearest neighbor closely follows the pseudocode for nearest neighbor in section \ref{tourconst}. The nearest neighbor implementation does not use the Array representation described in section \ref{array} above, but instead uses a single (ordinary) array to represent the tour. It uses the pre-calculated distances (see \ref{precalc}).

\pagebreak
\subsection{2-Opt Implementation}
For each vertex $v$ in $T$, $t_1$ is set to $v$ and \proc{Two-Optimal} is calculated as in the pseudocode in section \ref{2-optimal}. Lets call this the inner-loop. This inner loop is repeated $i$ times because there might be further improvements that should be evaluated.

The implementation of 2-Opt uses the neighbor list implementation described in section \ref{neighbor_lists}. When calculating $t_3$ we only loop through the closest neighbors of $t_1$ and not all vertices in the graph. This implementation will have the complexity $O(Nk+N^2)$ since we iterate through all the nodes in the outer loop and in the inner loop we both iterate through the neighbor list of $t_1$ and do a \proc{Flip}.

\subsection{3-Opt Implementation}
Our implementation is closely built on our 2-Opt implementation with a couple of additions and of course to find $t_5$ and $t_6$ in addition to $t_1,t_2,t_3$ and $t_4$ from 2-Opt. One of these is the method \proc{Between} (see \ref{TDS}). \proc{Between} is needed to make sure that $t_4$ is between $t_1$ and $t_6$ in the tour, if this is not the case, $t_5$ and $t_6$ is discarded and new value for these based on $t_4$ as usual. Further more we have to conclude what 3-change operation gives the best improvement to the tour (if any improvement is possible). This is done by simply comparing the original edges $(t_1,t_2)$, $(t_4,t_3)$ and $(t_6,t_5)$ to the possible new edges that can be created in every possible permutation (see \ref{3-change}). The actual 3-change operation to be executed is then done using two or three 2-change operations determined by what permutation is evaluated to give the most improvement. The complexity discussion for 3-Opt is similar to the that of 2-Opt with the differences that we iterate through the neighbor list of $t_4$ in addition to the neighbor list of $t_1$ and we do two or three flips instead of just one. This implies that the complexity for the 3-Opt implementation is $O(Nk^2+N^2)$.

\pagebreak
\section{Results}
In the Kattis tests below we have used nearest neighbor as tour construction and 3-Opt as optimization algorithm. Below $k$ is the size of the neighbor lists and $i$ is how many iterations we run 3-Opt on each test case. \emph{Time Limit Exceeded} is abbreviated as \emph{TLE}. Note that the scores are rounded to one decimal digit.

\begin{figure}[H]
	\centering
	\subfloat[$i = 5$]{\label{i5_table}
	\begin{tabular}{| l | c | c |}
	\hline
	$k$ & Score (p) & Time (s) \\
	\hline
	5 & 14.4 & 0.38 \\
	%\hline
	10 & 26.1 & 0.41 \\
	%\hline
	20 & 31.8 & 0.56 \\
	%\hline
	30 & 32.8 & 0.76 \\ 
	%\hline
	40 & 33.8 & 1.04 \\
	%\hline
	50 & 35.0 & 1.34\\
	\hline
	\end{tabular}}
	\hspace{20pt}
	\subfloat[$i = 10$]{\label{i10_table}
\begin{tabular}{| l | c | c |}
\hline
$k$ & Score (p) & Time (s) \\
\hline
5 & 16.2 & 0.38 \\
%\hline
10 & 26.5 & 0.46 \\
%\hline
20 & 32.4 & 0.67 \\
%\hline
30 & 33.1 & 1.07 \\ 
%\hline
40 & 34.0 & 1.64 \\
%\hline
50 & \emph{TLE} & \emph{TLE}\\
\hline
\end{tabular}}
\vspace{20pt}
\subfloat[$i = 15$]{\label{i15_table}
\begin{tabular}{| l | c | c |}
\hline
$k$ & Score (p) & Time (s) \\
\hline
5 & 16.2 & 0.40\\
%\hline
10 & 26.8 & 0.49 \\
%\hline
20 & 32.4 & 0.85 \\
%\hline
30 & 33.1 & 1.42 \\ 
%\hline
40 & \emph{TLE} & \emph{TLE} \\
%\hline
50 & \emph{TLE} & \emph{TLE} \\
\hline
\end{tabular}}
	\hspace{20pt}
	\subfloat[$i = 20$]{\label{i20_table}
\begin{tabular}{| l | c | c |}
\hline
$k$ & Score (p) & Time (s) \\
\hline
5 & 16.2 & 0.36\\
%\hline
10 & 26.9 & 0.53 \\
%\hline
20 & 32.4 & 1.00 \\
%\hline
30 & 33.1 & 1.74 \\ 
%\hline
40 & \emph{TLE} & \emph{TLE} \\
%\hline
50 & \emph{TLE} & \emph{TLE}\\
\hline
\end{tabular}}
\end{figure}


%\subfloat[i=?]{\label{i?_table}
%\begin{tabular}{| l | c | c |}
%\hline
%k & points & time(s) \\
%\hline
%5 & & \\
%\hline
%10 &  &  \\
%\hline
%20 &  &  \\
%\hline
%30 &  &  \\ 
%\hline
%40 &  &  \\
%\hline
%50 &  & \\
%\hline
%\end{tabular}}

With further testing on Kattis we were able to tweak the results. Our best result was achieved using 3-Opt with $k=50$ and $i=6$. With these values we managed to get 35 points in 1.53 seconds. The Kattis id for the test was 271476.

To our satisfaction this score placed us at tied first place in Kattis Java top list.

Below is a graph describing how the tour length changes with respect to changes in the size  $k$ of the neighbor lists. The test are made with 20 iterations on a test with the cites of Luxemburg. This test file has 980 vertices\footnote{Downloaded from \url{http://www.tsp.gatech.edu/world/lu980.tsp}}. The graph shows that there is no clear pattern between the value of $k$ and the tour length. A higher $k$ value means more neighbors are considered. There is an uncertainty to where these neighbors will be placed in the unsorted neighbor list and thus there is an uncertainty in what order the neighbors are considered. This could explain why there is no clear pattern in the graph.
\begin{center}
\begin{tikzpicture}
\begin{axis}[
xmin=5,
xmax=300,
ymax=12100,
yticklabel style={/pgf/number format/fixed,
                     /pgf/number format/precision=4},
xlabel=Size of neighbor lists,
ylabel=Tour length
]
\addplot[color=black,mark=*] coordinates {
(5, 13102)
(10, 12042)
(15, 11838)
(20, 11818)
(25, 11702)
(30, 11746)
(35, 11764)
(40, 11732)
(45, 11738)
(50, 11647)
(55, 11789)
(60, 11718)
(65, 11632)
(70, 11619)
(75, 11717)
(80, 11697)
(85, 11743)
(90, 11657)
(95, 11696)
(100, 11643)
(105, 11773)
(110, 11749)
(115, 11704)
(120, 11762)
(125, 11694)
(130, 11688)
(135, 11728)
(140, 11808)
(145, 11683)
(150, 11631)
(155, 11680)
(160, 11708)
(165, 11640)
(170, 11667)
(175, 11721)
(180, 11639)
(185, 11783)
(190, 11692)
(195, 11755)
(200, 11684)
(205, 11710)
(210, 11786)
(215, 11698)
(220, 11681)
(225, 11617)
(230, 11679)
(235, 11723)
(240, 11629)
(245, 11767)
(250, 11732)
(255, 11751)
(260, 11778)
(265, 11698)
(270, 11683)
(275, 11765)
(280, 11695)
(285, 11680)
(290, 11698)
(295, 11679)
(300, 11751)
};
\end{axis}
\end{tikzpicture}
\end{center}



% Further Improvements.
\section{Further Improvements} 


\subsection{Heap for Neighbor Lists}
If a heap were to be constructed to hold the neighbor list one could get a slight performance improvement in the creation of the lists. This would result in a sorted neighbor list. In our tests we evaluated the possible improvements of a sorted neighbor list by a less efficient algorithm and found that it yielded poorer result then the random list we ended up using. We think this was due to a tendency to get stuck in a local optimum that is further away from the global optimum. Though we are still a little perplexed why this happens.

\subsection{Dont'-look Bit}
\label{dl_bit}
With the \emph{don’t-look bit} one can further reduce the running time for 2-Opt and 3-Opt. This can however reduce the local optimum (similar to that of neighbor lists) \cite{tsp}. 

When considering a 2- or 3-Opt move for a vertex (as $t_1$) for which no improving move was found in a previous evaluation then it is improbable that the vertex will yield an improving move this time. The exception is when one of it's tour neighbors of this vertex has changed since it's last consideration.

The bits are stored for each vertex and are initially set to \const{false} \cite{algnotes}. 
The vertices with the don't look bit set to \const{false} are stored in a \emph{first-in first-out queue} (\emph{FIFO}) and processed when considering $t_1$ candidates for improving moves.
When a search for an improving move fails the bit for vertex $t_1$ is set to \const{true}. If the search is successful the bits for the vertices that are endpoints to a removed edge, that is $t_1$, $t_2$, $t_3$ and $t_4$ for 2-Opt and additionally $t_5$ and $t_6$ for 3-Opt, are set to \const{false} if previously \const{true}.

\subsection{Improving the Tour Data Structure}
An improvement of the running time for Arrays is to replace the edges $(a, b)$ and $(d, c)$ affected by the \proc{Flip}$(a, b, c, d)$ with the edges $(d, a)$ and $(c, b)$ (instead of $(a, d)$ and $(b, c)$ respectively), if the number of cities between $c$ and $a$ are fewer than the number of cities between $b$ and $d$. The worst case running time is still $\Theta(N)$ however \cite{dtsp}.

Another obvious improvement is to use the more advance data structure Two-Level Trees described in \ref{ds_theory} above to represent the tour.


\subsection{Better Construction Heuristic}
Greedy (see \ref{greedy}) but especially Christofides (see \ref{christo}) is supposed to achieve a better tour quality then the nearest neighbor algorithm \cite{tsp}. It is hard to foresee if the resulting tour length would decrease with a better initial tour after optimization. Since it is impossible to know what local optimum will be reached given a certain initial tour we are also unable to show that a shorter initial tour will converge toward a better local optimum then a random initial tour. Although one could suspect that a short initial tour would tend to give a shorter tour after optimization than a random tour.

Christofides produces the best initial tour but has a slow running time \cite{tsp}.

Due to the reasons mentioned above we are skeptical about the quality gained by a different construction heuristic and have not chosen to implement any such heuristic.

For the Euclidean TSP in two dimensions an improvement in the running time for nearest neighbor can be made using a data structure called a $k$-$d$ tree \cite{tsp}.


\subsection{Better Optimization Algorithm}
The Lin-Kernighan algorithm (see \ref{lk}) would most likely have yielded a better result than the algorithms we have implemented. Due to the time restrictions associated with this project we were not able to implement Lin-Kernighan.

% Conclusion.
\section{Conclusion} 
Our tests indicate that for $k \leq 30$ the solutions converge towards local optima with ten iterations. As seen in the results more iterations do not improve the length of the tour significantly. With larger $k$ values it is not possible to draw any conclusions because when $k>30$ we got time limit exceeded.

When testing on Kattis we noticed that increasing $k$ continued giving significantly larger score up to $k=50$. This could be interpreted to contradict the results from D.S. Johnson et al. which states that $k>20$ does not result in significantly improved tours \cite{tsp}. Since Kattis calculates score in such a way that a minor decrease in tour length percentage results in a significant score increase, when close to the optimal value, this is unlikely to be the case.

We have also noticed that it is easy to get stuck in local optimum and it is difficult to know what changes to $k$ and the number of iterations will trigger an improvement and what changes will result in a longer tour. This problem arises because neither 2-Opt or 3-Opt are able to escape a local optimum, unlike Lin-Kernighan (\ref{lk}). In the test we also saw that 3-Opt performed better than 2-Opt, this was expected since it corresponds with the extensive results provided by D.S. Johnson et al. \cite{tsp}.

If we manage to decrease the running time we could use the extra time to achieve a slightly higher score. This might have been done using the running time related improvements suggested above: a heap for the neighbor lists, don't look bits, a Two-Level Tree data structure for the tour and a $k$-$d$ tree for nearest neighbor.

For our implementation of 3-Opt, increasing $k$ and the number of iterations only gave slight improvements at this point. Thus, for any significant improvement, the next logical step would be to implement Lin-Kernighan.

%% Bibliography.
%\begin{thebibliography}{9}
%\bibitem{algnotes}
%  J. Håstad.
%  Notes for the course advanced algorithms, 2000, available at
%  <\url{http://www.csc.kth.se/utbildning/kth/kurser/DD2440/avalg07/algnotes.pdf}> (2012-01-05).
%\bibitem{tsp} % Full date 1995-11-20?
%  D.S. Johnson and L.A. McGeoch.
%  The Traveling Salesman Problem: A Case Study in Local Optimization, 1995, available at
%  <\url{http://www2.research.att.com/~dsj/papers/TSPchapter.pdf}> (2012-01-03).
%\bibitem{dtsp}
%  M.L. Fredman, D.S. Johnson, L.A. McGeoch and G. Ostheimer.
%  Data Structures for Traveling Salesmen.
%  \emph{J. Algorithms}, 18:3, pages 432--479, 1995, available at
%  <\url{http://www2.research.att.com/~dsj/papers/DTSP.pdf}> (2012-01-03).
%\bibitem{k_opt}
%  F. Mendivil , R. Shonkwiler and M. C. Spruill.
%  An analysis of Random Restart and Iterated Improvement for Global Optimization with an application to the Traveling Salesman Problem.
%  \emph{Journal of optimization theory and applications}, 124:4, pages 407--433, 2005, available at
%  <\url{http://people.math.gatech.edu/~shenk/Research/Optimization/RR+II.pdf}> (2012-01-04).
%\end{thebibliography}

\bibliography{references}{}
\bibliographystyle{plain}

\appendix

\end{document}
